public class HeapSort {


    /**
     * 堆的性质：本质上是一个数组，调整就是在数组上进行调整
     * 1. 完全二叉树(形式上，并非真是二叉树)
     * 2. 节点 >= 或者 <= 孩子节点；两个孩子节点无规律
     * 3. 根据数组进行创建堆
     * 4. 调整堆使用向下调整的方式（从最后一棵子树开始）
     * @param args
     */




    public static void main(String[] args) {
        int[] arr = {9,8,7,6,5,4,3,2,1,0};
        heapSort(arr);
        System.out.println();
    }


    /**
     * 排升序，建立大根堆
     * @param arr
     */
    public static void heapSort(int[] arr) {
        //1.建堆
        //2.不断交换堆顶和堆尾元素，队尾在变，如冒泡的最后一个元素一样

        createHeap(arr);
        int len = arr.length;
        for(int i=len-1;i>0;i--) {
            swap(arr,0,i); //堆顶、堆尾
            siftDown(arr,0,i); //向下调整一次,长度每次减1
        }
    }

    /**
     *  建堆方法 （大根堆）
     * @param arr
     */
    private static void createHeap(int[] arr) {
        int n = arr.length;
        int parent = (n-1-1)/2;  //最后一个节点索引为：n-1，然后根据孩子节点求父亲节点：(i-1)/2
        for(;parent>=0;parent--) { //从最后一棵子树慢慢向上调整
            siftDown(arr,parent,n);
        }
    }

    /**
     * 向下调整的方法
     */
    private static void siftDown(int[] arr,int parent,int len) {
        //1.找出左右孩子下标
        //2.找出左右孩子的最大那个（没有则小）
        //3.大的孩子和父节点比较，比父亲大则交换值
        //4.不断循环以上步骤 (交换后再判断交换后的子树)

        int child = 2 * parent + 1; //默认有左孩子 (一个孩子都没有就不是父节点)
        while (child < len) { //不断向下调整，直到下面的结构都满足大根堆
            if(child + 1 < len && arr[child+1] > arr[child]) { //假设存在右孩子 && 右孩子>左孩子
                child = child+1;
            }
            if(arr[child] > arr[parent]) { //需要交换
                swap(arr,parent,child);
                //交换下标，父子对调
                parent = child; //向下遍历。父节点向下沉
                child = parent*2 + 1;
            }else {
                break;
            }
        }
    }

    /**
     * 交换两个值
     * @param arr
     * @param i
     * @param j
     */
    private static void swap(int[] arr,int i,int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }



}
